GATE IT 2008

Q41.

The following is a code with two threads, producer and consumer, that can run in parallel. Further, S and Q are binary semaphores quipped with the standard P and V operations. semaphore S = 1, Q = 0; integer x; producer: consumer: while (true) do while (true) do P(S); P(Q); x = produce (); consume (x); V(Q); V(S); done done Which of the following is TRUE about the program above?
GateOverflow

Q42.

Which of the following is the negation of [\forall x, \alpha \rightarrow(\exists y, \beta \rightarrow(\forall u, \exists v, y))]
GateOverflow

Q43.

Which of the following first order formulae is logically valid? Here \alpha(x) is a first order formula with x as a free variable, and \beta is a first order formula with no free variable.
GateOverflow

Q44.

When n=2^{2 k} for some k \geqslant 0, the recurrence relation T(n)=\sqrt{(} 2) T(n / 2)+\sqrt{n}, T(1)=1 evaluates to :
GateOverflow

Q45.

Which of the following languages is (are) non-regular? L_1 = \{0^m1^n \mid 0 \leq m \leq n \leq 10000\} L_2 = \{w \mid w reads the same forward and backward\} L_3 = \{w \in \{0, 1\} ^* \mid w contains an even number of 0's and an even number of 1's\}
GateOverflow

Q46.

Consider the following relational schema:Student(school-id,sch-roll-no,sname,saddress) School(school-id,sch-name,sch-address,sch-phone) Enrolment(school-id,sch-roll-no,erollno,examname) ExamResult(erollno,examname,marks) Consider the following tuple relational calculus query. \begin{array}{l} \{t \mid \exists E \in \text { Enrolment } t=E \text { .school-id } \\ \wedge \mid\{x \mid x \in \text { Enrolment } \wedge x . \text { school-id }=t \wedge(\exists B \in \text { ExamResult } B . \text { erollno }=x . \text { erollno } \wedge B \\ \text { examname }=x . \text { examname } \wedge B . \text { marks }>35)\}|\div|\{x \mid x \in \text { Enrolment } \wedge x . \text { school-id }=t\} \mid \\ * 100>35\} \end{array}If a student needs to score more than 35 marks to pass an exam, what does the query return?
GateOverflow

Q47.

Which of the following regular expressions describes the language over\{0, 1\} consisting of strings that contain exactly two 1's?
GateOverflow

Q48.

Consider the field C of complex numbers with addition and multiplication. Which of the following form(s) a subfield of C with addition and multiplication? S1: the set of real numbers S2:\{(a + ib) \mid a and b are rational numbers\} S3:\{a + ib \mid (a^2 + b^2) \leq 1\} S4: \{ia \mid a \text{ is real}\}
GateOverflow

Q49.

If we use Radix Sort to sort n integers in the range \left (n^{k/2}, n^k \right ), for some k>0 which is independent of n, the time taken would be?
GateOverflow

Q50.

Consider the following relational schema:Student(school-id,sch-roll-no,sname,saddress) School(school-id,sch-name,sch-address,sch-phone) Enrolment(school-id,sch-roll-no,erollno,examname) ExamResult(erollno,examname,marks) What does the following SQL query output?SELECT sch-name, COUNT (*) FROM School C, Enrolment E, ExamResult R WHERE E.school-id = C.school-id AND E.examname = R.examname AND E.erollno = R.erollno AND R.marks = 100 AND S.school-id IN (SELECT school-id FROM student GROUP BY school-id HAVING COUNT (*) > 200) GROUP By school-id
GateOverflow